/**
 * Created by L.jp
 * Description:小红拿到了一颗二叉树，定义每个节点的价值为子树节点乘积的末尾0的数量。现在请你返回一颗二叉树，树的结构和给定二叉树相同，将每个节点的权值替换为该节点的价值。
 *  *
 *  * 二叉树的节点不超过10^5。
 *  *
 *  * 二叉树每个节点的权值都是不超过10^9的正整数。
 *  *
 *  * 示例1
 *  *
 *  * 输入
 *  *
 *  * {2,5,10,#,#,4,5}
 *  * 输出
 *  *
 *  * {3,0,2,#,#,0,0}
 *  * 说明
 *  *
 *  * 小红拿到的树
 *  *                        2
 *  *                      /   \
 *  *                     5     10
 *  *                          /  \
 *  *                         4    5
 *  * 需要返回的树
 *  *         3
 *  *        /  \
 *  *       0    2
 *  *           / \
 *  *          0   0
 * User: 86189
 * Date: 2023-04-20
 * Time: 23:16
 */
public class Solution {
    //详细思路：当前节点的权值等于子树节点乘积末尾0的个数（根据题意需要乘上当前的节点），其实也就是计算因子2和5的个数的最小值
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public class Solution2 {
        public TreeNode valueOfTree(TreeNode root) {
            dfs(root);
            return root;
        }
        private int[] dfs(TreeNode node) {
            if (node == null) {
                return new int[]{0,0};
            }
            int[] l = dfs(node.left);
            int[] r = dfs(node.right);
            int[] cur = cal(node.val);
            int n2 = cur[0] + l[0] + r[0];
            int n5 = cur[1] + l[1] + r[1];
            node.val = Math.min(n2, n5);
            return new int[]{n2,n5};
        }
        //末尾0的数量与因子2和5的数量关系
        private int[] cal(int num) {
            int n2 = 0, n5 = 0;
            while (num % 2 == 0) {
                num /= 2;
                n2 += 1;
            }
            while (num % 5 == 0) {
                num /= 5;
                n5 += 1;
            }
            return new int[]{n2,n5};
        }
    }
}
